﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Hungarian_Matching
{
    public class FindAugmentPath
    {
        static int n = 0, m = 0;//数组左边,右边的顶点数目

        /// <summary>
        /// 从顶点start开始寻找增广路径
        /// </summary>
        /// <param name="map">二分图</param>
        /// <param name="used"></param>
        /// <param name="linked">左边顶点与右边顶点的连接</param>
        /// <param name="start"></param>
        /// <returns></returns>
        static bool DFS(int[,] map, bool[] used, int[] linked, int start)
        {
            for (int i = 0; i < m; i++)
            {
                if (!used[i] && map[start, i] == 1)
                {
                    used[i] = true;
                    if (linked[i] == -1 || DFS(map, used, linked, i))
                    {
                        linked[start] = i;
                        return true;
                    }
                }
            }

            //if (linked[start] != -1)
            //    linked[start] = -1;
            return false;
        }

        static int GetMaxNum(int[,] map)
        {
            int count = 0;
            int[] linked = new int[m];
            for (int i = 0; i < m; i++)
                linked[i] = -1; //默认左边和右边顶点均未匹配

            for (int i = 0; i < n; i++)//从左边第一个顶点开始匹配
            {
                bool[] used = new bool[m];//设定右边顶点均可以匹配
                if (DFS(map, used, linked, i))
                    count++;
            }

            for (int i = 0; i < linked.Length; i++)
                Console.WriteLine("N:{0} - M:{1}", i, linked[i]);

            return count;
        }


        public static void Run()
        {
            n = 3;
            m = 3;

            //构造二分图,使用3x3数组来代替顶点
            int[,] map = new int[n, m];

            //  Below combination can not get the correct answer?
            //--------------------------------
            //map[0, 0] = 1;
            //map[0, 1] = 1;
            //map[1, 0] = 1;
            //map[1, 2] = 1;
            //map[2, 1] = 1;
            //---------------------------------------------------

            map[0, 0] = 1;
            map[0, 1] = 1;
            map[1, 1] = 1;
            map[1, 2] = 1;
            map[2, 1] = 1;
            //map[2, 0] = 1;

            var rest = GetMaxNum(map);
        }

    }
}
